package problems.contest;

import java.util.*;

/**
 * 第340场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-340</p>
 *
 * @author dubulingbo, 2023/4/9 10:27.
 */
public class WCT340 {
    /**
     * T1|6361. 对角线上的质数
     * <p>https://leetcode.cn/problems/prime-in-diagonal/</p>
     */
    public int diagonalPrime(int[][] nums) {
        int n = nums.length;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            if (max < nums[i][i] && isPrime(nums[i][i])) {
                max = nums[i][i];
            }
            if (max < nums[i][n - 1 - i] && isPrime(nums[i][n - 1 - i])) {
                max = nums[i][n - 1 - i];
            }
        }

        return max;
    }

    private boolean isPrime(int k) {
        if (k < 2) return false;

        int q = (int) Math.sqrt(k);

        for (int i = 2; i <= q; ++i) {
            if (k % i == 0) return false;
        }

        return true;
    }


    /**
     * T2|6360. 等值距离和
     * <p>https://leetcode.cn/problems/sum-of-distances/</p>
     */
    public long[] distance(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            List<Integer> list = map.get(nums[i]);
            if (list == null) {
                list = new ArrayList<>();
                list.add(i);
                map.put(nums[i], list);
            } else {
                list.add(i);
            }
        }

        long[] arr = new long[n];
        for (Map.Entry<Integer, List<Integer>> e : map.entrySet()) {
            List<Integer> vals = e.getValue();
            if (vals != null && vals.size() > 1) {
                int sz = vals.size();
                long[] dp = new long[sz];

                for (int i = sz - 2; i >= 0; --i) {
                    dp[i] = dp[i + 1] + (long) (sz - 1 - i) * (vals.get(i + 1) - vals.get(i));
                }

                long preSum = 0;
                for (int i = 0; i < sz; ++i) {
                    if (i > 0) {
                        preSum += (long) i * (vals.get(i) - vals.get(i - 1));
                    }
                    arr[vals.get(i)] = preSum + dp[i];
                }
            }

        }

        return arr;
    }


    /**
     * T3|6359. 最小化数对的最大差值
     * <p>https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/</p>
     */
    public int minimizeMax(int[] nums, int p) {
        int n = nums.length;
        if (n < 2 || p < 1) return 0;

        Arrays.sort(nums);

        int left = 0, right = nums[n - 1] - nums[0];
        // 标记数组
        boolean[] vis = new boolean[n];

        // 二分搜索每一个值
        while (left < right) {
            int mid = left + (right - left) / 2;
            Arrays.fill(vis, false);
            int pair = 0;

            for (int i = 1, j = 0; pair < p && i < n; ++i) {
                while (j < i && (nums[i] - nums[j] > mid || vis[j])) ++j;
                if (j < i) {
                    // 找到一对 <= mid 差值对
                    vis[i] = true;
                    vis[j] = true;
                    ++pair;
                }
            }

            // 当前枚举的 mid 已经找到了 p 对差值对，可能还会有更小的
            if (pair == p) right = mid;
                // 没有找到 <= mid 的 p 对差值对，需要扩大查找范围
            else left = mid + 1;
        }

        return left;
    }

    /**
     * T4|6353. 网格图中最少访问的格子数
     * <p>https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/</p>
     */
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 处理特殊情况
        if (m < 2 && n < 2) return 1;

        Queue<int[]> que = new ArrayDeque<>();
        int[][] dis = new int[m][n];
        que.offer(new int[]{0, 0});
        dis[0][0] = 1;

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                int[] d = que.poll();
                int cx = d[0];
                int cy = d[1];

                for (int x = cx + 1; x < m && x <= cx + grid[cx][cy]; ++x) {
                    if (dis[x][cy] == 0) {
                        // 没访问过
                        que.offer(new int[]{x, cy});
                        dis[x][cy] = dis[cx][cy] + 1;
                        // 到达目标点
                        if (x == m - 1 && cy == n - 1) return dis[x][cy];
                    }
                }

                for (int y = cy + 1; y < n && y <= cy + grid[cx][cy]; ++y) {
                    if (dis[cx][y] == 0) {
                        // 没访问过
                        que.offer(new int[]{cx, y});
                        dis[cx][y] = dis[cx][cy] + 1;
                        // 到达目标点
                        if (cx == m - 1 && y == n - 1) return dis[cx][y];
                    }
                }
            }
        }

        return -1;
    }
}